In order to reduce the entries of routing tables and avoid using large numbers of Virtual Channels (VC), a Region-based Fault Tolerant Routing (RFTR) algorithm was proposed for wormhole switching 2D Mesh Network on Chip (NoC) to reduce the amount of hardware resources. According to the positions of faulty nodes and links, the 2D Mesh network was divided into several rectangular regions. Within each region the packet could be routed by deterministic or adaptive routing algorithms, while among these regions the routing path was determined by up ^*/down ^* routing algorithm. Besides, with the Channel Dependency Graph (CDG) model, the proposed algorithm was proved to be deadlock-free using only two VCs. In a 6×6 Mesh network, the RFTR algorithm can reduce the amount of routing table resources by 25%. Simulation results show that, with the same amount of buffer resources, the RFTR algorithm can achieve an equivalent or even higher performance compared to up ^*/down ^* and segment-based routing algorithms.